package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class RecoverBinarySearchTree {
	
	/*This is the solution get from nine chapter, pretty neat and clean.*/
	// Keep comparing with the last visited element
	// Nothing fancy, just the inorder traversal
	private TreeNode first = null;
	private TreeNode second = null;
	private TreeNode last = new TreeNode(Integer.MIN_VALUE);
	
	public void recoverTree(TreeNode root) {
		traverse(root);
		swap();
	}
	
	private void traverse(TreeNode root) {
		if (root == null) return;
		
		traverse(root.left);
		
		// there are 2 cases
		/*
		 *    1, 2, 3, 4, 5
		 *    
		 *    switch 2 and 4
		 *    1 4 3 2 5  -> 2 bumps
		 *    switch 1 and 2
		 *    2 1 3 4 5 -> 1 bump
		 *    
		 *         3
		 *     1     4
		 *       2     5
		 * 
		 */
		if (first == null && root.val < last.val) {
			// Note this is the last visited element
			first = last;
		}
		// this will work on this case, 1 bump, parent case
		//      0
		//     /
		//   1
		if (first != null && root.val < last.val) {
			second = root;
		}
		
		// Update the last updated element
		last = root;
		traverse(root.right);
	}
	// swap value, not pointer
	private void swap() {
		int temp = first.val;
		first.val = second.val;
		second.val = temp;
	}
	
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode child = new TreeNode(1);
        root.left = child;
        
        RecoverBinarySearchTree rbst = new RecoverBinarySearchTree();
        // rbst.recoverTreeWithLinearSpace(root);
        rbst.recoverTree(root);
        
        
    }
}


